#include <bits/stdc++.h>

using namespace std;




struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
//根据vector值构建二叉树
TreeNode * gou(vector<int> num){
    if(num.size()==0) return nullptr;
    TreeNode *root=new TreeNode(num[0]);
    queue<TreeNode*> s;
    s.push(root);
    int index=1,len=num.size();
    while(!s.empty()&&index<len){
        TreeNode *p=nullptr,*q=nullptr;
        p=new TreeNode(num[index++]);
        if(index<len) q=new TreeNode(num[index++]);
        TreeNode *r=s.front();s.pop();
        r->left=p;r->right=q;
        s.push(p),s.push(q);
    }
    return root;
}


//序列化二叉树？
//时间超限？内存超限？？
class Codec1 {
    string res;
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        res.append("[");
        if(root==nullptr){
            res.append("]");
            return res;
        }
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
            TreeNode *p=que.front();que.pop();
            if(p!=nullptr){
                res.append(to_string(p->val)+",");
                que.push(p->left);
                que.push(p->right);
            }else{
                res.append("null,");
            }
        }
        res=res.substr(0,res.length()-1);
        res.append("]");
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data=="[]") return nullptr;
        data=data.substr(data.find_first_not_of("["));
        data=data.substr(0,data.find_last_not_of("]")+1);
        vector<string> v;v.clear();
        while(data.find(",")!=string::npos){
            int index=data.find(",");
            string tp=data.substr(0,index);
            data=data.substr(index+1);
            v.push_back(tp);
        }
        v.push_back(data);
        int index=1;

        TreeNode *root=new TreeNode(stoi(v[0]));
       
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty() ){
            TreeNode *p=que.front();que.pop();
            if(v[index]!="null"){
                TreeNode *tmp=new TreeNode(stoi(v[index]));
                p->left=tmp;
                que.push(tmp);
            }
            index++;
            if(v[index]!="null"){
                TreeNode *tmp=new TreeNode(stoi(v[index]));
                p->right=tmp;
                que.push(tmp);
            }
            index++;
        }
        return root;
    }
};

//序列化二叉树？
//不直接操作字符串
class Codec {
   
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        ostringstream out;
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
            TreeNode *tmp=que.front();que.pop();
            if(tmp){
                out << tmp->val << " ";
                que.push(tmp->left);
                que.push(tmp->right);
            }else{
                out<< "null ";
            }
        }
        return out.str();
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream inp(data);
        string tmp;
        vector<TreeNode*> v;
        while(inp>> tmp){
            if(tmp == "null"){
                v.push_back(nullptr);
            }else{
                v.push_back(new TreeNode(stoi(tmp)));
            }
        }
        int j=1,len=v.size();
        for(int i=0;j<len;++i){
            if(v[i]==nullptr) continue;
            if(j<len) v[i]->left=v[j++];
            if(j<len) v[i]->right=v[j++];
        }
        return v[0];
    }
};







TreeNode* g(){
    TreeNode *root=new TreeNode(1);
    root->left=new TreeNode(2);
    root->right=new TreeNode(3);
    TreeNode *p=root->right;
    p->left=new TreeNode(4);
    p->right=new TreeNode(5);
    return root;
}


int main(){
    TreeNode *root=g();
    Codec1 c;

    string x=c.serialize(root);
    cout << x <<endl;
    c.deserialize(x);



    return 0;
}